Ambiguous grammar Totally Explained

Everything about Ambiguous Grammar totally explained

In computer science, a grammar is said to be an ambiguous grammar if there's some string that it can generate in more than one way (for example, the string has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars. Some programming languages have ambiguous grammars; in this case, semantic information is needed to select the intended parse of an ambiguous construct. For example, in C the following:
x * y ;
can be interpreted either as the declaration of an identifier y of type pointer to x, or as an expression in which x is multiplied by y and the result is discarded. To choose between the two possible interpretations, a compiler must consult its symbol table to find out whether x has been declared as a typedef name that's visible at this point.

Example

The context free grammar ť A → A + A | A − A | a

is ambiguous since there are two leftmost derivations for the string a + a + a:

A	→ A + A	A	→ A + A
	→ a + A		→ A + A + A
	→ a + A + A		→ a + A + A
	→ a + a + A		→ a + a + A
	→ a + a + a		→ a + a + a

As another example, the grammar is ambiguous since there are two parse trees for the string a + a − a: ť

The language that it generates, however, isn't inherently ambiguous; the following is a non-ambiguous grammar generating the same language: ť A → A + a | A − a | a

Recognizing an ambiguous grammar

The general question of whether a grammar isn't ambiguous is undecidable. No algorithm can exist to determine the ambiguity of a grammar because if so, the undecidable Post correspondence problem could be encoded as an ambiguity problem.
There is an obvious difficulty in parsing an ambiguous grammar by a deterministic parser (see deterministic context-free grammar) but nondeterministic parsing imposes a great efficiency penalty. Most constructs of interest to parsing can be recognized by unambiguous grammars. Some ambiguous grammars can be converted into unambiguous grammars, but no general procedure for doing this is possible just as no algorithm exists for detecting ambiguous grammars. Compiler generators such as YACC include features for disambiguating some kinds of ambiguity, such as by using the precedence and associativity constraints.

Inherently ambiguous languages

While some languages (the set of strings that can be generated by a grammar) have both ambiguous and unambiguous grammars, there exist languages for which no unambiguous grammar can exist. An example of an inherently ambiguous language is the union of

which is the intersection of the two languages.

Further Information

Get more info on 'Ambiguous Grammar'.

External Link Exchanges

Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:

<a href="http://ambiguous_grammar.totallyexplained.com">Ambiguous grammar Totally Explained</a>

Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned.